//
//  Code2.swift
//  cnswift-demo
//
//  Created by YangWei on 2021/1/7.
//  Copyright © 2021 YangWei. All rights reserved.
//

import UIKit

/**
 两数相加
 
 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

 请你将两个数相加，并以相同形式返回一个表示和的链表。

 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/add-two-numbers
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Code2: Base {
    
    func run() {
        // [2,4,3] + [5,6,4]
        let node1 = ListNode(2)
        node1.next = ListNode(4)
        node1.next?.next = ListNode(3)

        let node2 = ListNode(5)
        node2.next = ListNode(6)
        node2.next?.next = ListNode(4)
        
        let result = addTwoNumbers(node1, node2)
        print(node1.strValue(), "+", node2.strValue(), "=" , result?.strValue() as Any)
        
        // [0] + [0]
        let node3 = ListNode(0)
        let node4 = ListNode(0)
        let result2 = addTwoNumbers(node3, node4)
        print(node3.strValue(), "+", node4.strValue(), "=", result2?.strValue() as Any)
        
        // [9,9,9,9,9,9,9] + [9,9,9,9]
        let node5 = ListNode(nums: [9,9,9,9,9,9,9])
        let node6 = ListNode(nums: [9,9,9,9])
        let result3 = addTwoNumbers(node5, node6)
        print(node5.strValue(), "+", node6.strValue(), "=", result3?.strValue() as Any)
    }
    
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        
        if l1 == nil && l2 != nil {
            return l2
        }
        
        if l1 != nil && l2 == nil {
            return l1
        }
        
        if l1 == nil && l2 == nil {
            return nil
        }
        
        var reslutNode: ListNode?
        
        let initValue = l1!.val + l2!.val
        var carry = 0
        if initValue >= 10 {
            reslutNode = ListNode(initValue % 10)
            carry = 1
        } else {
            reslutNode = ListNode(initValue)
        }
        
        // 指向需要追加的节点
        var resultPointNext = reslutNode
        
        var l1NodeNext = l1!.next
        var l2NodeNext = l2!.next
        
        while (l1NodeNext != nil || l2NodeNext != nil || carry != 0) {
           var nextNode:ListNode?
            
            var l1Value = 0
            if let node1 = l1NodeNext {
                l1Value = node1.val
                l1NodeNext = l1NodeNext?.next
            }
            var l2Value = 0
            if let node2 = l2NodeNext {
                l2Value = node2.val
                l2NodeNext = l2NodeNext?.next
            }
            let resultValue = l1Value + l2Value + carry
            if resultValue >= 10 {
                carry = 1
                nextNode = ListNode(resultValue % 10)
            } else {
                carry = 0
                nextNode = ListNode(resultValue)
            }
            
            resultPointNext?.next = nextNode
            resultPointNext = nextNode
        }
        
        return reslutNode
    }
}

class ListNode {
    var val: Int
    var next: ListNode?
    init() {
        self.val = 0
        self.next = nil
    }
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
    init(_ val: Int, _ next: ListNode?) {
        self.val = val
        self.next = next
    }
    init(nums: [Int]) {
        self.val = nums[0]
        var lastNode = self
        for num in 1..<nums.count {
            let nextNode = ListNode(nums[num])
            lastNode.next = nextNode
            lastNode = nextNode
        }
    }
    func strValue() -> String {
        var numStr = "\(self.val)"
        var node = self.next
        while node != nil {
            numStr += String(describing: node!.val)
            node = node?.next
        }
        return "[" + numStr + "]"
    }
}
